package com.wang.utils.recursion;

/**
 * @author 10570
 * @date 2021/7/28 22:32
 */

/**
 *  8*8 的棋盘
 * 八皇后问题，
 *  两个皇后不能存在同一行或同一列或同一斜线上
 *  回溯的时候是，第一个皇后放在第一列的所有位置的正确解法  之后一次放在其他行得到最终结果
 */
public class EightQueueDemo {

    //定义一个max，共有多少皇后
    int max = 8;
    static int count = 0;
    static int judgeCount = 0;
    //定义一个数组，保存正确结果
    int[] array = new int[max];
    public static void main(String[] args) {
        EightQueueDemo demo = new EightQueueDemo();
        demo.check(0);
        System.out.println("一共的判断次数"+judgeCount);
        System.out.println("一个的解法："+count);
    }
    //编写方法，放置皇后
    //每一次check都会进行一次for循环
    public void check(int n){
        //8个皇后就放好了
        if (n == max){
            print();
            count++;

            return;
        }
        for (int i = 0; i < max; i++){
            //将皇后放到第一列
            array[n] = i;
            //放置n个皇后要判断是否冲突
            if (judge(n)){
                check(n+1);
            }
            //冲突就array[n] 就放到本行的后一个位置
        }
    }
    //判断是否冲突,摆到第n个皇后，需要与前面的皇后比较
    public boolean judge(int n){
        judgeCount++;
        for (int i = 0 ; i < n;i++){
            //Math.abs() 求绝对值
            //Math.abs(n-i) == Math.abs(array[n] - array[i]  表示 第n个皇后是否与 第i个皇后 在同一斜线
            //不需要判断同一行，n在一直增
            if (array[i] == array[n] ||
                    Math.abs(n-i) == Math.abs(array[n] - array[i])){  //同一列
                return false;
            }
        }
        return true;
    }

    //将皇后放的位置打印
    private void print(){
        for (int i = 0; i< array.length; i++){
            System.out.print(array[i] + " " );
        }
        System.out.println();
    }
}
